package com.topcoder.srm198;

import java.util.Comparator;
import java.util.PriorityQueue;

public class DungeonEscape {
	private final static int 		INF = 25000;
	private int 					M;
	private int 					N;
	private int[][] 				up, down, east, west;
	private PriorityQueue<State>	pq;
	private int[][]					times;
	
	public int exitTime(String[] up, String[] down, String[] east, String[] west, int startLevel, int startEasting) {
		M = up.length;
		N = up[0].length();
		this.up = new int[M][N];
		this.down = new int[M][N];
		this.east = new int[M][N];
		this.west = new int[M][N];
		this.times = new int[M+1][N];
		
		for (int i=0; i<M; i++) {
			for (int j=0; j<N; j++) {
				this.up[i][j] = up[i].charAt(j)=='x'? INF : up[i].charAt(j) - '0';
				this.down[i][j] = down[i].charAt(j)=='x'? INF : down[i].charAt(j) - '0';
				this.east[i][j] = east[i].charAt(j)=='x'? INF : east[i].charAt(j) - '0';
				this.west[i][j] = west[i].charAt(j)=='x'? INF : west[i].charAt(j) - '0';
			}
		}
		for (int i=0; i<M+1; i++) {
			for (int j=0; j<N; j++) {
				times[i][j] = INF;
			}
		}
		
		pq = new PriorityQueue<State>(10, new Comparator<State>() {
			public int compare(State a, State b) {
				return a.time - b.time;
			}
		});
		pq.add(new State(startLevel+1, startEasting, 0));
		
		while (!pq.isEmpty()) {
			State s = pq.remove();
			if (s.x == 0) return s.time;
			if (times[s.x][s.y] >= s.time) {
				visit(s.x-1, s.y, s.time, this.up[s.x-1][s.y]);
				visit(s.x+1, s.y, s.time, this.down[s.x-1][s.y]);
				visit(s.x, s.y-1, s.time, this.west[s.x-1][s.y]);
				visit(s.x, s.y+1, s.time, this.east[s.x-1][s.y]);
			}
		}
		
		return -1;
	}
	
	private void visit(int x, int y, int time, int cost) {
		if (x < 0 || x > M || y < 0 || y >= N || (x>0 && time+cost >= (M-x+1)*N)) return;
		if (times[x][y] > time + cost) {
			pq.add(new State(x, y, time + cost));
			times[x][y] = time + cost;
		}
	}
	
	private class State {
		int x, y, time;
		public State(int x, int y, int time) {
			this.x = x;
			this.y = y;
			this.time = time;
		}
	}
}
